﻿#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <stack>
#include <unordered_set>
#include <queue>
using namespace std;

//一.数组相关题目

//1.轮转数组 https://leetcode.cn/problems/rotate-array
void rotate(vector<int>& nums, int k);

//2.删除有序数组中的重复项 https://leetcode.cn/problems/remove-duplicates-from-sorted-array
int removeDuplicates(vector<int>& nums);

//3.数组形式的整数加法 https://leetcode.cn/problems/add-to-array-form-of-integer
vector<int> addToArrayForm(vector<int>& num, int k);

//4.乘积最大子数组 https://leetcode.cn/problems/maximum-product-subarray/description/
int maxProduct(vector<int>& nums);

//5.多数元素 https://leetcode.cn/problems/majority-element/description/
int majorityElement(vector<int>& nums);

//6.存在重复元素 https://leetcode.cn/problems/contains-duplicate/
bool containsDuplicate(vector<int>& nums);

//7.搜索二维矩阵 https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
bool searchMatrix(vector<vector<int>>& matrix, int target);



//二.链表相关题目
struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

//8.反转链表 https://leetcode.cn/problems/reverse-linked-list/description/
ListNode* reverseList(ListNode* head);

//9.移除链表元素 https://leetcode.cn/problems/remove-linked-list-elements/description/
ListNode* removeElements(ListNode* head, int val);

//10.链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list/description/
ListNode* middleNode(ListNode* head);

//11.删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
ListNode* removeNthFromEnd(ListNode* head, int n);

//12.合并两个有序链表 https://leetcode.cn/problems/merge-two-sorted-lists/description/
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2);

//13.回文链表 https://leetcode.cn/problems/aMhZSa/description/
bool isPalindrome(ListNode* head);

//14.相交链表 https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB);

//15.环形链表 https://leetcode.cn/problems/linked-list-cycle/description/
bool hasCycle(ListNode* head);

//16.随机链表的复制 https://leetcode.cn/problems/copy-list-with-random-pointer/description/
Node* copyRandomList(Node* head);



//三、栈和队列相关题目

//17.有效的括号 https://leetcode.cn/problems/valid-parentheses/description/
bool isValid(string s);

//18.用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues/description/
class MyStack;

//19.设计循环队列 https://leetcode.cn/problems/design-circular-queue/description/
class MyCircularQueue;

//20.最小栈 https://leetcode.cn/problems/min-stack/
class MinStack;

//21.验证栈序列 https://leetcode.cn/problems/validate-stack-sequences/description/
bool validateStackSequences(vector<int>& pushed, vector<int>& popped);



//四、树相关题目
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

//22.二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
class Solution_preorderTraversal;

//23.二叉树的中序遍历 https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
class Solution_inorderTraversal;

//24.二叉树的后序遍历 https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
class Solution_postorderTraversal;

//25.二叉树构建与遍历 https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpld=60&&tqld=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
class buildBinaryTreeAndInorderTraversal;

//26.平衡二叉树 https://leetcode.cn/problems/balanced-binary-tree/description/
class Solution_isBalanced;

//27.相同的树 https://leetcode.cn/problems/same-tree/description/
class Solution_isSameTree;

//28.翻转二叉树 https://leetcode.cn/problems/invert-binary-tree/description/
class Solution_invertTree;

//29.二叉树的层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
class Solution_levelOrder;

//30.二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
class Solution_lowestCommonAncestor;

//31.二叉搜索树与双向链表 https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpld=13&&tqld=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
class Solution_Convert;

//32.从前序与中序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
class Solution_buildTree;